package main.leetcode.clockin.September;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 51. N 皇后
 *
 * <p>n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * <p>给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 *
 * <p>每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * <p>提示：皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
 */
public class day3 {
    private final List<List<String>> res = new ArrayList<>();
    private final Set<Integer> y = new HashSet<>();
    private final Set<Integer> b1 = new HashSet<>();
    private final Set<Integer> b2 = new HashSet<>();
    private String template;
    private int n;

    public static void main(String[] args) {
        System.out.println(new day3().solveNQueens(4));
        System.out.println(new day3().solveNQueens(1));
    }

    public List<List<String>> solveNQueens(int n) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            builder.append(".");
        }
        template = builder.toString();
        this.n = n;
        // 以行递归
        dfs(0, new ArrayList<>());
        return res;
    }

    private void dfs(int i, List<String> cur) {
        if (i == n) {
            res.add(new ArrayList<>(cur));
            return;
        }

        StringBuilder stringBuilder = new StringBuilder(template);
        // 以列循环
        for (int j = 0; j < n; ++j) {
            if (y.contains(j) || b1.contains(j + i) || b2.contains(j - i)) {
                continue;
            }
            stringBuilder.setCharAt(j, 'Q');
            y.add(j);
            b1.add(j + i);
            b2.add(j - i);
            cur.add(stringBuilder.toString());
            dfs(i + 1, cur);
            // 回溯
            cur.remove(cur.size() - 1);
            b2.remove(j - i);
            b1.remove(j + i);
            y.remove(j);
            stringBuilder.setCharAt(j, '.');
        }
    }
}
